package club.vann.leetcode.race;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * <p>难度：Hard</p>
 * <p>题目：找到最接近目标值的函数值</p>
 * <p>描述：Winston 构造了一个如上所示的函数 func 。他有一个整数数组 arr 和一个整数 target ，他想找到让 |func(arr, l, r) - target| 最小的 l 和 r 。
 *
 * 请你返回 |func(arr, l, r) - target| 的最小值。
 *
 * 请注意， func 的输入参数 l 和 r 需要满足 0 <= l, r < arr.length 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：arr = [9,12,3,7,15], target = 5
 * 输出：2
 * 解释：所有可能的 [l,r] 数对包括 [[0,0],[1,1],[2,2],[3,3],[4,4],[0,1],[1,2],[2,3],[3,4],[0,2],[1,3],[2,4],[0,3],[1,4],[0,4]]， Winston 得到的相应结果为 [9,12,3,7,15,8,0,3,7,0,0,3,0,0,0] 。最接近 5 的值是 7 和 3，所以最小差值为 2 。
 * 示例 2：
 *
 * 输入：arr = [1000000,1000000,1000000], target = 1
 * 输出：999999
 * 解释：Winston 输入函数的所有可能 [l,r] 数对得到的函数值都为 1000000 ，所以最小差值为 999999 。
 * 示例 3：
 *
 * 输入：arr = [1,2,4,8,16], target = 0
 * 输出：0
 *
 *
 * 提示：
 *
 * 1 <= arr.length <= 10^5
 * 1 <= arr[i] <= 10^6
 * 0 <= target <= 10^7</p>
 * Created with IntelliJ IDEA.
 * User: fanyu
 * Date: 2020/7/19
 * Time: 11:25
 * To change this template use File | Settings | File Templates.
 * Description:
 */
public class LeetCode_5467 {
    public static void main(String[] args) {
        LeetCode_5467 leetCode = new LeetCode_5467();

        System.out.println("Result["+TestCase.ANS+"] : " + leetCode.closestToTarget(TestCase.ARR, 5));
        System.out.println("Result["+TestCase.ANS1+"] : " + leetCode.closestToTarget(TestCase.ARR1, 1));
        System.out.println("Result["+TestCase.ANS2+"] : " + leetCode.closestToTarget(TestCase.ARR2, 0));
        System.out.println("Result["+TestCase.ANS3+"] : " + leetCode.closestToTarget(TestCase.ARR3, 14));
    }

    private class SegmentTree {
        int[] tree;
        int n;
        public SegmentTree(int[] nums) {
            if (nums.length > 0) {
                n = nums.length;
                tree = new int[n * 2];
                buildTree(nums);
            }
        }
        private void buildTree(int[] nums) {
            for (int i = n, j = 0;  i < 2 * n; i++,  j++) {
                tree[i] = nums[j];
            }

            for (int i = n - 1; i > 0; --i) {
                tree[i] = tree[i * 2] & tree[i * 2 + 1];
            }
        }

        public int sumRange(int l, int r) {
            // get leaf with value 'l'
            l += n;
            // get leaf with value 'r'
            r += n;
            int sum = Integer.MAX_VALUE;
            while (l <= r) {
                if ((l % 2) == 1) {
                    sum &= tree[l];
                    l++;
                }
                if ((r % 2) == 0) {
                    sum &= tree[r];
                    r--;
                }
                l /= 2;
                r /= 2;
            }
            return sum;
        }
    }

    public int closestToTarget(int[] arr, int target) {
        SegmentTree tree = new SegmentTree(arr);
        int res = Integer.MAX_VALUE, len = arr.length;
        for (int i = 0; i < len; ++i) {
            int st = i, ed = len - 1;
            while (st + 1 < ed) {
                int mid = (st + ed) / 2;
                int sum = tree.sumRange(i, mid);
                if (sum == target) {
                    return 0;
                } else if (sum > target) {
                    st = mid;
                } else {
                    ed = mid;
                }
            }
            res = Math.min(res, Math.min(Math.abs(tree.sumRange(i, st) - target), Math.abs(tree.sumRange(i, ed) - target)));
        }
        return res;
    }

    /**
     * 解法二：
     *
     * @param arr
     * @param target
     * @return
     */
    public int closestToTarget1(int[] arr, int target) {
        ArrayList<Integer> list = new ArrayList<>();
        for (int i : arr) {
            if (list.isEmpty() || i != list.get(list.size() - 1)) {
                list.add(i);
            }
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < list.size(); i++) {
            int X = list.get(i);
            for (int j = i; j < list.size(); j++) {
                X &= list.get(j);
                ans = Math.min(ans, Math.abs(target - X));
                if (X <= target) {
                    break;
                }

            }
        }
        return ans;
    }

    static class TestCase {
        public static int ANS = 2;
        public static int[] ARR = {9,12,3,7,15};

        public static int ANS1 = 999999;
        public static int[] ARR1 = {1000000,1000000,1000000};

        public static int ANS2 = 0;
        public static int[] ARR2 = {1,2,4,8,16};

        public static int ANS3 = 1;
        public static int[] ARR3 = {131071,16383,1023,65535,63,2047,524287,63,31,16383,131071,15,15,32767,127,127,63,4095,4095,1023,511,131071,524287,31,8191,31,31,511,63,31,524287,15,16383,32767,65535,262143,65535,255,127,262143,8191,2047,1023,255,16383,15,524287,8191,8191,31,31,32767,4095,32767,1023,15,4095,127,4095,8191,131071,131071,1023,15,65535,16383,31,65535,127,8191,524287,16383,31,16383,131071,127,32767,32767,65535,15,524287,1023,65535,15,31,16383,15,255,31,511,127,524287,32767,1023,8191,1023,127,131071,65535,32767,63,262143,524287,63,524287,524287,262143,524287,63,32767,16383,15,31,131071,262143,32767,131071,255,2047,1023,1023,63,2047,127,127,4095,4095,131071,524287,15,2047,63,8191,31,63,65535,524287,4095,4095,65535,32767,255,2047,2047,8191,15,262143,32767,131071,255,262143,2047,65535,15,262143,16383,2047,127,127,63,524287,63,127,127,2047,15,8191,255,131071,1023,127,255,255,511,255,262143,31,4095,15,8191,15,63,255,31,32767,32767,131071,31,8191,15,32767,511,63,524287,15,127,262143,131071,511,524287,511,511,511,127,2047,524287,524287,1023,255,63,255,127,131071,262143,63,255,511,131071,31,127,15,2047,511,2047,4095,63,4095,1023,511,511,65535,63,16383,262143,15,127,32767,1023,511,8191,63,511,65535,31,1023,31,511,524287,2047,4095,32767,2047,255,255,127,2047,8191,32767,1023,524287,65535,524287,255,4095,65535,2047,65535,255,31,32767,1023,63,131071,127,4095,16383,4095,8191,262143,127,131071,31,16383,255,255,1023,262143,262143,262143,131071,15,63,16383,65535,32767,262143,2047,2047,524287,63,16383,511,32767,32767,15,255,65535,255,524287,262143,1023,1023,31,262143,32767,262143,524287,255,63,4095,31,524287,2047,4095,524287,65535,2047,1023,511,32767,2047,1023,511,32767,1023,1023,15,511,2047,524287,511,131071,511,2047,524287,15,2047,8191,31,131071,63,31,31,1023,524287,16383,2047,131071,524287,255,255,524287,31,131071,511,524287,511,32767,127,4095,255,8191,16383,1023,2047,8191,15,15,65535,65535,131071,131071,262143,8191,15,1023,4095,31,511,8191,2047,31,65535,127,262143,32767,1023,65535,131071,65535,127,16383,4095,65535,127,127,31,255,2047,2047,131071,63,8191,255,127,4095,16383,131071,4095,65535,1023,255,15,127,4095,1023,262143,2047,16383,262143,16383,2047,15,8191,1023,32767,4095,63,511,262143,131071,32767,2047,1023,16383,15,524287,65535,65535,15,63,31,65535,2047,131071,4095,31,2047,524287,1023,65535,2047,32767,31,63,255,262143,2047,2047,127,262143,131071,4095,262143,32767,32767,2047,4095,2047,15,1023,32767,2047,511,15,32767,63,16383,32767,8191,15,2047,32767,255,127,511,1023,255,127,131071,15,127,127,65535,65535,63,131071,131071,31,15,511,255,16383,2047,65535,1023,255,511,255,2047,8191,255,262143,16383,255,255,31,131071,65535,65535,255,511,63,31,255,524287,16383,131071,1023,8191,262143,4095,1023,15,511,63,63,511,127,524287,2047,524287,32767,524287,63,262143,255,131071,511,31,127,16383,255,131071,65535,16383,262143,65535,255,31,32767,31,8191,31,255,15,127,262143,16383,127,15,15,511,8191,131071,4095,65535,524287,63,15,511,2047,1023,255,511,63,255,31,255,524287,63,8191,4095,255,2047,131071,255,255,127,32767,8191,262143,65535,255,2047,15,131071,8191,127,524287,63,16383,127,255,262143,32767,4095,2047,65535,65535,4095,524287,15,262143,524287,31,255,1023,262143,4095,511,131071,524287,15,31,65535,131071,32767,15,4095,262143,31,127,4095,15,63,511,16383,63,31,1023,524287,31,2047,15,15,31,255,15,255,16383,2047,127,31,1023,127,65535,15,2047,31,127,65535,127,1023,8191,4095,2047,15,8191,524287,524287,8191,4095,4095,131071,32767,131071,127,127,8191,1023,511,127,255,2047,511,32767,131071,524287,63,32767,255,65535,16383,1023,511,511,524287,65535,262143,1023,255,31,4095,511,2047,2047,262143,1023,63,63,31,15,131071,127,524287,1023,524287,2047,15,31,1023,131071,31,131071,255,2047,16383,65535,32767,1023,524287,63,2047,127,63,524287,63,31,524287,8191,131071,4095,1023,4095,511,2047,511,65535,2047,4095,2047,2047,255,2047,16383,2047,2047,32767,16383,1023,16383,65535,16383,255,8191,65535,511,15,65535,1023,131071,131071,262143,65535,4095,127,65535,31,65535,4095,65535,16383,255,262143,255,511,131071,524287,2047,63,2047,15,127,8191,16383,15,32767,4095,2047,65535,32767,1023,8191,32767,15,8191,1023,15,2047,65535,32767,16383,63,511,65535,524287,65535,65535,127,63,16383,8191,127,2047,262143,255,8191,8191,255,32767,2047,32767,2047,8191,2047,2047,15,1023,16383,15,32767,262143,65535,65535,65535,524287,1023,262143,31,16383,255,15,262143,31,127,1023,8191,524287,131071,131071,63,255,63,131071,1023,16383,32767,511,32767,8191,65535,131071,131071,524287,8191,63,524287,2047,16383,524287,4095,511,511,2047,255,524287,524287,2047,2047,8191,255,131071,31,8191,131071,262143,524287,127,65535,15,524287,31,524287,131071,2047,65535,262143,131071,2047,15,1023,524287,2047,262143,131071,4095,65535,131071,8191,131071,524287,32767,65535,262143,127,255,131071,262143,15,1023,8191,4095,8191,31,4095,31,127,63,16383,63,63,131071,511,262143,262143,131071,4095,2047,16383,32767,8191,65535,31,2047,65535,65535,511,1023,255,31,63,511,2047,16383,255,2047,2047,1023,8191,2047,2047,63,127,511,8191,131071,127,16383,1023,4095,255,65535,15,63,131071,524287,16383,255,511,65535,8191,511,131071,65535,4095,511,65535,15,15,65535,2047,262143,32767,2047,4095,524287,262143,8191,4095,31,255,15,2047,524287,31,8191,31,262143,524287,511,1023,262143,255,63,524287,31,15,31,31,16383,15,511,32767,262143,255,65535,63,262143,1023,32767,511,16383,127,262143,127,131071,63,31,8191,63,32767,31,1023,127,127,8191,524287,255,511,32767,131071,8191,255,16383,262143,15,31,1023,4095,1023,31,63,2047,524287,1023,255,2047,524287,262143,65535,131071,262143,63,524287,127,16383,127,32767,15,65535,16383,65535,524287,511,4095,511,32767,255,524287,8191,65535,262143,511,262143,8191,15,32767,131071,65535,8191,31,511,511,8191,2047,8191,63,255,65535,32767,131071,127,262143,262143,255,31,524287,255,16383,32767,1023,4095,15,131071,262143,32767,16383,524287,524287,511,63,31,16383,255,15,31,2047,4095,4095,16383,65535,131071,262143,1023,4095,524287,1023,63,8191,8191,511,4095,31,63,127,32767,511,32767,524287,511,4095,32767,255,131071,255,32767,255,63,511,524287,127,1023,15,262143,524287,524287,127,127,511,131071,15,4095,511,15,32767,131071,131071,65535,1023,16383,31,4095,8191,16383,63,65535,131071,31,2047,8191,4095,16383,127,15,8191,511,16383,16383,255,524287,2047,8191,262143,16383,127,524287,524287,524287,8191,131071,255,63,4095,2047,15,255,31,16383,127,31,127,2047,262143,2047,255,255,262143,524287,63,2047,1023,31,4095,32767,511,65535,32767,65535,131071,131071,16383,15,511,32767,131071,524287,262143,31,15,1023,16383,8191,16383,8191,32767,1023,4095,63,65535,31,524287,262143,15,15,16383,8191,1023,511,1023,63,63,127,255,4095,255,255,524287,65535,16383,524287,524287,1023,32767,63,255,131071,8191,2047,524287,65535,63,63,4095,511,131071,15,511,32767,4095,16383,65535,65535,4095,131071,255,32767,511,8191,255,31,4095,524287,4095,8191,511,524287,511,32767,32767,32767,8191,63,15,31,255,15,15,63,255,1023,262143,262143,16383,1023,255,31,1023,8191,16383,31,31,16383,2047,32767,16383,255,262143,4095,524287,524287,65535,2047,511,511,511,127,65535,131071,262143,8191,262143,16383,1023,127,63,255,32767,127,255,511,16383,524287,524287,524287,1023,2047,31,4095,31,8191,63,4095,15,511,15,1023,131071,4095,32767,1023,524287,8191,255,131071,255,8191,32767,262143,32767,4095,65535,262143,1023,255,65535,8191,16383,32767,8191,511,524287,511,1023,32767,255,524287,63,127,262143,65535,127,262143,255,127,524287,524287,15,2047,2047,16383,16383,1023,16383,255,32767,4095,127,2047,63,511,15,4095,65535,255,524287,31,31,8191,65535,2047,4095,524287,63,127,4095,63,1023,15,127,131071,262143,32767,127,31,131071,511,511,262143,255,262143,4095,524287,524287,2047,65535,255,65535,1023,32767,31,255,127,262143,15,1023,4095,1023,63,65535,127,262143,16383,2047,1023,4095,65535,127,1023,1023,1023,32767,255,8191,8191,31,65535,127,4095,131071,1023,4095,255,255,63,15,65535,131071,15,2047,1023,511,511,511,524287,16383,131071,63,524287,4095,255,4095,127,511,131071,15,31,31,255,262143,2047,15,127,131071,8191,4095,16383,1023,31,255,524287,4095,262143,16383,4095,524287,63,65535,65535,15,65535,2047,16383,4095,16383,1023,15,511,511,65535,4095,15,127,2047,255,262143,16383,15,131071,255,31,262143,15,255,31,15,262143,1023,15,16383,524287,15,31,31,4095,262143,2047,32767,16383,16383,131071,63,131071,4095,8191,16383,4095,1023,15,1023,4095,15,4095,65535,255,1023,63,65535,262143,16383,4095,15,2047,32767,511,255,15,127,262143,2047,2047,4095,65535,1023,4095,65535,4095,524287,262143,1023,8191,262143,63,31,524287,32767,16383,31,15,255,65535,2047,1023,31,511,262143,15,15,1023,31,32767,1023,31,4095,63,524287,8191,15,8191,8191,63,4095,31,15,127,524287,524287,16383,262143,65535,4095,2047,65535,511,31,2047,16383,65535,127,32767,131071,4095,15,31,2047,8191,4095,31,2047,127,8191,127,31,8191,524287,2047,65535,1023,32767,127,2047,32767,511,1023,32767,524287,524287,4095,127,255,127,131071,262143,15,1023,2047,511,127,262143,31,262143,262143,32767,524287,31,65535,262143,32767,65535,131071,8191,4095,1023,1023,524287,8191,63,32767,8191,8191,65535,131071,63,511,131071,2047,15,4095,1023,32767,131071,65535,31,524287,127,262143,16383,127,262143,15,262143,1023,1023,255,511,31,524287,4095,2047,255,524287,127,1023,15,262143,63,4095,262143,16383,127,2047,31,4095,255,262143,127,63,2047,4095,15,262143,8191,32767,262143,255,131071,127,131071,131071,255,63,16383,131071,15,8191,1023,15,31,131071,2047,15,32767,255,511,524287,255,127,31,127,511,31,4095,127,262143,262143,65535,15,8191,524287,15,15,131071,524287,2047,127,8191,4095,255,255,1023,8191,524287,511,63,31,131071,63,65535,262143,255,131071,65535,65535,2047,15,8191,15,8191,16383,63,127,131071,4095,511,63,127,32767,4095,131071,65535,15,32767,16383,127,1023,524287,4095,524287,16383,65535,15,65535,16383,32767,15,65535,8191,262143,65535,8191,65535,255,31,524287,8191,2047,127,127,131071,15,262143,31,8191,131071,524287,511,262143,4095,4095,1023,255,16383,32767,31,262143,127,8191,32767,127,262143,131071,31,524287,511,131071,511,1023,8191,65535,65535,16383,255,131071,65535,262143,65535,1023,15,1023,16383,131071,4095,262143,262143,2047,2047,524287,1023,1023,1023,15,131071,2047,63,1023,131071,1023,63,8191,15,15,32767,63,32767,65535,511,255,262143,65535,16383,255,16383,4095,16383,262143,65535,1023,255,255,63,131071,524287,31,8191,511,15,511,524287,2047,15,511,262143,524287,511,31,131071,127,63,15,4095,131071,127,511,511,4095,8191,4095,4095,2047,63,16383,15,524287,2047,262143,4095,8191,127,65535,131071,16383,63,16383,65535,524287,32767,2047,2047,131071,65535,31,1023,65535,131071,262143,262143,65535,31,1023,255,16383,16383,131071,8191,15,63,4095,63,65535,131071,255,16383,1023,4095,8191,8191,511,32767,31,255,131071,255,15,65535,2047,32767,4095,65535,524287,131071,511,127,511,127,8191,255,16383,2047,15,8191,4095,63,511,8191,262143,15,63,31,255,2047,262143,524287,127,131071,524287,255,262143,131071,2047,127,63,255,524287,65535,262143,31,2047,131071,15,8191,31,31,131071,65535,15,32767,32767,8191,2047,262143,511,262143,4095,8191,131071,131071,32767,4095,511,2047,63,65535,127,65535,4095,255,32767,32767,63,16383,511,8191,524287,31,15,16383,127,8191,2047,31,65535,262143,524287,2047,16383,127,65535,32767,2047,511,524287,511,32767,524287,15,16383,32767,255,127,1023,2047,8191,4095,127,1023,131071,32767,511,255,255,127,31,2047,31,32767,31,8191,63,15,511,63,262143,1023,32767,131071,511,4095,255,32767,524287,1023,511,127,255,511,15,2047,127,4095,524287,131071,131071,2047,524287,31,63,63,524287,524287,524287,262143,65535,127,524287,16383,63,4095,8191,1023,4095,1023,131071,65535,65535,32767,65535,16383,2047,63,65535,15,1023,4095,2047,16383,15,524287,4095,2047,511,1023,16383,8191,131071,524287,8191,255,1023,65535,2047,16383,16383,262143,32767,131071,524287,511,4095,32767,65535,524287,16383,262143,16383,2047,2047,15,127,65535,32767,1023,63,127,2047,32767,65535,15,63,262143,8191,65535,4095,4095,31,4095,65535,8191,262143,16383,1023,8191,131071,511,8191,262143,255,127,16383,511,15,8191,31,63,131071,255,131071,511,2047,1023,1023,31,32767,16383,15,511,63,262143,8191,255,63,511,63,524287,31,255,16383,127,16383,32767,15,15,511,127,65535,511,131071,511,4095,511,262143,65535,16383,127,15,65535,2047,524287,127,65535,127,131071,524287,127,1023,127,1023,127,8191,262143,2047,127,8191,8191,2047,511,262143,127,8191,131071,31,524287,511,8191,63,8191,63,15,31,16383,131071,8191,1023,1023,63,127,8191,255,32767,127,127,65535,65535,15,8191,524287,131071,127,65535,16383,2047,4095,2047,131071,524287,4095,2047,262143,63,2047,255,32767,8191,131071,127,262143,524287,32767,255,16383,4095,65535,524287,65535,131071,511,2047,2047,255,511,16383,511,31,524287,63,31,524287,32767,2047,1023,131071,524287,16383,127,63,31,65535,2047,255,31,255,127,131071,8191,131071,32767,16383,127,8191,131071,63,63,31,262143,4095,65535,4095,63,255,31,262143,1023,511,63,131071,32767,1023,262143,255,32767,255,511,127,15,131071,262143,8191,63,65535,8191,15,4095,127,65535,127,131071,1023,15,2047,65535,262143,131071,262143,8191,127,65535,127,8191,8191,65535,4095,15,32767,4095,4095,262143,262143,262143,255,4095,255,63,131071,1023,31,8191,31,262143,131071,4095,16383,524287,262143,2047,2047,524287,65535,2047,65535,255,32767,131071,65535,511,32767,16383,2047,4095,262143,15,31,16383,1023,524287,16383,511,131071,1023,8191,131071,511,511,1023,15,4095,8191,1023,131071,4095,1023,511,131071,63,255,2047,4095,262143,65535,16383,127,16383,127,131071,31,65535,16383,63,8191,127,63,4095,131071,16383,31,31,127,255,32767,15,4095,8191,255,524287,15,255,262143,131071,65535,131071,15,63,262143,65535,1023,4095,2047,4095,131071,127,32767,255,511,131071,8191,1023,262143,16383,127,31,8191,63,511,65535,511,2047,511,32767,511,524287,524287,4095,127,127,255,65535,262143,524287,8191,127,15,262143,131071,8191,262143,255,131071,2047,4095,262143,4095,131071,32767,31,2047,524287,15,31,4095,511,255,16383,32767,131071,511,2047,2047,2047,131071,127,131071,16383,131071,16383,2047,4095,15,511,31,127,524287,15,32767,2047,131071,127,255,65535,511,2047,524287,262143,16383,63,63,16383,511,1023,511,16383,32767,63,65535,1023,16383,8191,16383,262143,4095,32767,15,262143,8191,131071,524287,65535,32767,1023,4095,262143,31,65535,8191,2047,65535,4095,255,15,31,63,16383,1023,31,511,511,255,511,65535,4095,1023,524287,31,127,2047,255,2047,32767,127,262143,524287,255,16383,524287,4095,4095,255,16383,63,31,511,1023,31,16383,255,524287,65535,65535,262143,2047,131071,127,63,8191,31,31,16383,4095,255,31,65535,127,131071,8191,4095,127,511,16383,255,8191,262143,127,4095,255,2047,2047,8191,524287,65535,32767,2047,8191,31,511,15,511,1023,2047,32767,16383,1023,63,1023,255,15,63,262143,4095,4095,63,262143,16383,16383,63,8191,31,15,524287,1023,63,255,262143,15,65535,15,31,524287,524287,16383,511,16383,2047,1023,32767,63,8191,8191,255,32767,131071,16383,16383,32767,131071,127,31,65535,8191,8191,127,524287,511,2047,262143,32767,127,262143,511,1023,524287,63,32767,8191,31,63,511,16383,131071,255,262143,32767,4095,511,32767,4095,131071,31,524287,16383,511,262143,1023,8191,8191,63,127,63,8191,131071,32767,32767,255,127,4095,131071,8191,63,63,32767,511,2047,524287,31,511,524287,131071,131071,511,65535,31,63,127,4095,32767,524287,16383,524287,131071,15,524287,127,65535,63,255,511,131071,65535,32767,255,65535,2047,15,32767,16383,65535,131071,255,65535,8191,524287,15,127,524287,511,511,524287,127,15,32767,31,255,1023,255,131071,131071,2047,1023,127,32767,131071,4095,15,1023,127,127,65535,31,511,1023,63,65535,65535,32767,1023,8191,2047,63,255,65535,255,15,262143,8191,127,31,32767,255,524287,8191,131071,32767,262143,524287,15,15,2047,255,2047,65535,255,63,131071,1023,31,65535,131071,255,511,2047,4095,4095,255,4095,65535,8191,63,16383,524287,4095,31,127,31,524287,131071,4095,127,255,127,255,32767,2047,127,63,15,4095,511,524287,8191,131071,1023,1023,31,1023,1023,511,1023,31,255,2047,2047,32767,1023,511,255,16383,4095,16383,1023,31,32767,65535,131071,127,262143,8191,1023,32767,15,65535,32767,511,127,65535,4095,127,4095,63,524287,524287,524287,4095,131071,1023,511,31,15,65535,65535,32767,2047,16383,2047,16383,2047,524287,255,131071,4095,31,32767,511,511,255,16383,255,16383,8191,8191,31,31,262143,1023,511,127,255,15,63,8191,65535,16383,524287,255,1023,63,2047,524287,131071,4095,32767,15,511,262143,15,524287,127,8191,127,32767,15,8191,131071,16383,524287,8191,4095,2047,65535,65535,255,131071,255,8191,127,1023,511,65535,511,8191,32767,127,255,255,16383,4095,511,8191,127,131071,524287,65535,1023,511,1023,32767,255,63,511,262143,511,131071,4095,32767,63,31,127,1023,65535,262143,131071,524287,131071,131071,63,2047,262143,16383,32767,262143,127,262143,63,511,63,15,2047,131071,16383,131071,31,262143,131071,31,511,1023,65535,2047,32767,31,2047,131071,63,65535,1023,1023,16383,2047,65535,131071,127,65535,8191,511,65535,32767,15,255,2047,524287,2047,16383,63,63,127,524287,255,15,262143,2047,63,31,262143,524287,4095,16383,255,31,16383,65535,262143,63,2047,15,8191,127,16383,32767,8191,127,16383,524287,1023,524287,31,16383,2047,127,2047,63,524287,262143,127,32767,131071,15,255,65535,2047,32767,511,127,4095,511,16383,31,262143,65535,16383,15,15,255,131071,4095,31,16383,31,8191,2047,65535,2047,511,255,16383,262143,511,63,63,131071,524287,2047,131071,1023,4095,511,2047,8191,2047,255,255,524287,65535,15,15,4095,16383,32767,8191,2047,65535,511,1023,8191,524287,65535,511,31,63,262143,524287,16383,16383,16383,16383,511,1023,4095,2047,15,4095,8191,524287,63,2047,15,8191,8191,8191,4095,15,262143,31,262143,32767,63,4095,511,16383,63,4095,16383,2047,16383,4095,65535,524287,16383,262143,63,8191,4095,131071,31,255,31,63,1023,255,1023,127,255,16383,63,8191,1023,511,131071,63,131071,131071,16383,8191,262143,8191,63,524287,31,1023,1023,63,262143,2047,32767,255,2047,32767,131071,524287,16383,2047,32767,4095,31,511,511,63,15,511,31,524287,127,32767,524287,15,8191,131071,511,63,255,1023,2047,65535,511,15,131071,65535,127,2047,15,1023,262143,4095,127,255,8191,1023,65535,31,524287,1023,262143,15,511,524287,15,16383,31,63,127,63,1023,131071,1023,63,32767,8191,127,262143,32767,8191,63,31,131071,131071,8191,31,4095,16383,511,131071,31,4095,16383,1023,8191,32767,32767,1023,131071,127,262143,262143,262143,1023,4095,32767,65535,8191,63,31,511,131071,31,262143,131071,511,31,15,524287,15,8191,127,1023,131071,131071,2047,2047,255,262143,31,63,16383,4095,4095,127,262143,255,511,8191,4095,16383,63,255,65535,131071,511,1023,32767,2047,63,131071,15,4095,127,127,31,524287,255,4095,15,4095,32767,2047,31,127,262143,511,524287,31,2047,131071,262143,31,4095,31,2047,262143,524287,16383,131071,4095,63,16383,32767,16383,1023,32767,31,2047,31,255,1023,1023,32767,131071,511,63,1023,262143,1023,131071,127,63,511,131071,31,1023,262143,131071,2047,1023,4095,127,511,15,255,511,524287,131071,65535,2047,31,511,511,16383,15,1023,15,2047,16383,31,2047,15,8191,524287,32767,4095,511,65535,511,4095,32767,15,31,65535,31,32767,65535,262143,511,8191,255,127,4095,15,511,262143,32767,32767,511,4095,262143,8191,65535,2047,15,65535,127,4095,255,131071,524287,8191,127,4095,63,4095,511,32767,262143,32767,2047,65535,262143,65535,65535,255,65535,4095,31,511,2047,16383,127,1023,1023,1023,2047,31,15,4095,31,1023,1023,31,511,524287,8191,32767,31,131071,31,524287,15,127,8191,2047,4095,63,1023,4095,4095,63,32767,262143,524287,127,262143,2047,31,65535,63,1023,131071,131071,262143,31,15,32767,255,262143,16383,1023,127,16383,262143,127,8191,4095,8191,524287,262143,16383,524287,4095,32767,524287,31,32767,2047,127,32767,16383,131071,31,31,8191,31,1023,262143,255,32767,511,32767,127,262143,15,32767,524287,524287,8191,63,2047,8191,32767,255,524287,16383,32767,65535,1023,262143,524287,4095,2047,127,65535,262143,1023,31,511,31,127,255,16383,65535,4095,16383,262143,511,127,131071,1023,511,1023,2047,511,31,15,511,1023,15,15,127,127,65535,524287,15,2047,63,2047,262143,65535,31,32767,511,4095,131071,262143,31,31,524287,63,524287,511,524287,32767,4095,2047,16383,2047,32767,8191,31,255,15,262143,4095,1023,262143,131071,15,8191,1023,1023,15,255,511,1023,4095,2047,131071,1023,4095,16383,32767,32767,63,524287,511,255,255,131071,4095,63,131071,131071,524287,511,32767,511,127,127,31,63,32767,4095,262143,2047,1023,16383,31,16383,65535,127,2047,31,262143,255,511,127,511,63,31,8191,16383,524287,15,524287,524287,65535,15,511,131071,524287,31,16383,4095,32767,8191,511,65535,1023,2047,131071,31,511,16383,8191,4095,31,32767,524287,65535,8191,63,16383,8191,63,63,31,65535,1023,31,262143,1023,511,2047,131071,32767,65535,63,63,2047,65535,4095,15,15,255,8191,262143,511,65535,4095,524287,15,4095,16383,63,127,31,1023,2047,511,31,31,16383,511,262143,16383,4095,262143,2047,15,1023,63,15,16383,127,63,32767,16383,8191,255,16383,2047,63,131071,16383,65535,31,127,16383,8191,262143,63,127,16383,32767,262143,255,31,131071,16383,131071,131071,127,32767,4095,511,262143,4095,127,127,131071,262143,4095,511,2047,65535,63,2047,524287,262143,63,524287,262143,131071,262143,511,1023,1023,255,63,511,32767,32767,65535,262143,32767,255,16383,262143,65535,511,524287,15,511,1023,32767,32767,511,31,255,4095,63,2047,16383,65535,31,1023,63,1023,32767,63,8191,4095,2047,255,1023,65535,4095,8191,2047,262143,524287,262143,8191,262143,524287,16383,16383,65535,524287,32767,65535,8191,15,511,2047,255,1023,32767,63,16383,63,262143,63,524287,4095,31,1023,65535,65535,131071,262143,8191,4095,31,4095,4095,131071,31,262143,511,31,127,524287,15,32767,16383,63,63,15,2047,524287,131071,15,524287,1023,8191,16383,127,32767,262143,16383,16383,8191,4095,127,262143,1023,4095,65535,255,63,4095,262143,31,32767,255,65535,127,262143,32767,65535,4095,2047,262143,65535,65535,16383,524287,4095,63,16383,4095,65535,255,1023,2047,31,262143,262143,4095,131071,2047,65535,262143,127,65535,15,131071,2047,31,15,1023,524287,65535,524287,31,255,31,4095,127,2047,65535,15,131071,262143,511,16383,1023,262143,15,15,524287,511,31,16383,262143,2047,15,2047,511,16383,511,131071,31,131071,1023,127,131071,524287,131071,127,31,15,127,524287,8191,1023,131071,262143,32767,63,8191,63,524287,31,255,1023,2047,15,63,524287,65535,63,127,255,255,63,65535,15,4095,63,32767,2047,511,63,262143,131071,15,524287,131071,511,131071,63,15,4095,127,2047,131071,16383,31,4095,31,511,127,65535,255,65535,2047,31,511,63,127,2047,31,31,1023,32767,127,15,32767,8191,16383,65535,262143,2047,511,131071,255,511,127,2047,2047,262143,16383,127,127,31,32767,127,8191,31,65535,524287,65535,63,2047,127,63,131071,16383,31,32767,65535,63,131071,32767,131071,262143,65535,4095,15,524287,16383,131071,1023,524287,65535,4095,32767,16383,255,511,8191,8191,4095,31,255,8191,31,1023,31,15,255,127,2047,31,127,32767,255,65535,4095,31,511,2047,8191,8191,15,31,16383,32767,127,31,255,32767,1023,16383,32767,32767,65535,511,262143,511,127,31,65535,15,524287,65535,511,262143,31,16383,4095,255,32767,31,1023,15,127,15,131071,2047,524287,255,8191,262143,255,16383,63,255,63,63,1023,511,524287,1023,63,131071,255,8191,15,16383,255,524287,31,2047,262143,127,255,8191,127,2047,131071,511,15,15,262143,127,131071,8191,1023,63,63,2047,8191,65535,4095,63,32767,524287,127,524287,1023,32767,32767,127,131071,15,131071,31,262143,255,8191,32767,63,524287,511,2047,65535,1023,65535,63,32767,63,127,524287,255,32767,2047,63,2047,511,511,511,262143,2047,63,63,2047,511,1023,63,524287,262143,65535,4095,65535,255,255,65535,15,32767,127,255,32767,511,4095,524287,127,511,255,4095,511,1023,8191,524287,65535,16383,31,63,65535,255,65535,63,15,131071,32767,262143,1023,511,511,4095,131071,127,15,2047,32767,63,2047,1023,511,524287,131071,8191,4095,65535,255,65535,2047,255,4095,127,8191,31,262143,255,1023,15,63,1023,16383,2047,15,4095,1023,31,8191,4095,127,63,255,1023,1023,262143,262143,32767,1023,16383,2047,15,1023,65535,255,15,32767,63,255,16383,511,524287,511,1023,524287,16383,8191,262143,511,15,131071,127,8191,15,2047,255,15,131071,511,4095,31,262143,65535,15,32767,511,4095,262143,1023,524287,32767,2047,4095,32767,262143,16383,4095,16383,65535,262143,511,63,255,16383,31,131071,2047,8191,1023,131071,131071,8191,8191,2047,8191,1023,63,32767,524287,511,2047,4095,511,4095,131071,65535,255,511,262143,16383,32767,127,32767,31,65535,63,32767,8191,4095,4095,63,63,16383,4095,262143,15,131071,1023,63,4095,15,8191,1023,1023,16383,4095,15,2047,1023,255,63,63,255,31,255,511,262143,63,16383,63,16383,31,63,31,16383,2047,1023,2047,16383,32767,2047,32767,131071,1023,65535,15,4095,65535,65535,511,2047,15,8191,65535,511,1023,2047,511,131071,131071,31,255,63,15,4095,63,262143,65535,63,255,262143,255,65535,2047,127,31,31,31,65535,127,255,32767,2047,15,15,511,4095,4095,65535,32767,16383,16383,32767,131071,63,32767,16383,2047,32767,63,32767,31,8191,1023,524287,15,1023,2047,2047,511,31,15,131071,4095,31,511,524287,16383,255,524287,8191,31,63,127,65535,16383,15,2047,15,2047,262143,262143,4095,255,524287,131071,63,31,31,2047,4095,131071,4095,4095,511,8191,8191,262143,127,524287,16383,31,8191,1023,524287,262143,127,4095,4095,131071,255,255,127,127,2047,262143,15,511,127,255,4095,16383,16383,8191,511,255,1023,15,32767,2047,1023,131071,2047,31,511,262143,1023,63,2047,8191,127,131071,262143,15,32767,32767,4095,131071,31,8191,31,63,524287,127,4095,262143,255,15,1023,16383,255,131071,255,15,4095,131071,127,131071,16383,127,15,16383,2047,2047,511,2047,31,262143,262143,255,511,32767,127,63,511,32767,131071,127,63,32767,2047,63,63,255,127,131071,32767,16383,511,16383,127,31,65535,255,15,4095,32767,524287,15,4095,1023,16383,8191,32767,255,8191,65535,63,1023,16383,262143,127,8191,255,255,8191,8191,1023,127,15,8191,262143,1023,1023,15,511,4095,127,15,511,524287,65535,63,524287,63,131071,511,63,32767,4095,127,4095,31,15,31,8191,127,127,2047,16383,511,31,131071,255,65535,8191,32767,255,32767,2047,255,262143,15,16383,31,63,131071,32767,15,32767,131071,262143,4095,2047,15,15,524287,31,15,511,127,2047,131071,131071,127,16383,511,127,1023,127,65535,255,2047,524287,8191,16383,511,31,63,8191,2047,255,4095,524287,127,8191,255,127,32767,65535,15,127,8191,31,16383,255,15,127,255,511,16383,2047,511,524287,65535,15,15,2047,1023,32767,31,31,63,255,131071,524287,16383,16383,1023,2047,8191,511,32767,127,127,32767,31,2047,524287,32767,1023,511,15,511,32767,127,16383,255,16383,255,511,1023,524287,131071,131071,32767,8191,1023,16383,16383,65535,127,255,63,65535,15,32767,65535,511,262143,16383,15,63,65535,63,262143,65535,255,15,2047,127,31,2047,65535,2047,1023,65535,4095,31,1023,4095,131071,63,131071,16383,127,63,262143,524287,255,255,65535,2047,511,262143,127,15,63,131071,131071,127,131071,65535,127,8191,32767,63,63,31,4095,131071,31,8191,131071,8191,524287,127,8191,127,262143,65535,524287,4095,511,255,524287,131071,262143,65535,255,15,255,2047,15,255,65535,262143,15,131071,31,8191,4095,511,31,2047,16383,2047,8191,4095,16383,63,524287,8191,32767,16383,2047,63,4095,63,1023,255,255,15,8191,131071,4095,8191,16383,131071,524287,65535,255,255,32767,127,255,65535,2047,131071,63,16383,511,4095,65535,8191,63,65535,2047,8191,131071,127,131071,8191,63,255,15,262143,2047,16383,16383,127,511,31,32767,2047,16383,262143,131071,2047,262143,8191,511,255,63,31,1023,262143,127,1023,31,511,262143,524287,131071,127,255,8191,15,524287,127,1023,16383,2047,4095,524287,2047,63,31,524287,63,32767,4095,4095,262143,32767,1023,15,131071,131071,524287,65535,255,511,65535,65535,511,131071,8191,4095,131071,1023,524287,255,511,8191,8191,2047,131071,4095,4095,524287,1023,2047,8191,15,255,524287,65535,16383,1023,15,63,511,16383,4095,16383,127,255,31,63,16383,15,15,65535,15,255,31,31,2047,255,31,32767,524287,524287,16383,1023,16383,511,15,8191,262143,15,16383,16383,127,16383,262143,127,31,65535,131071,8191,127,16383,511,31,127,16383,131071,31,1023,8191,65535,1023,15,2047,4095,131071,2047,127,255,32767,524287,16383,15,65535,15,32767,127,127,511,262143,4095,127,262143,8191,524287,16383,255,1023,2047,127,16383,2047,4095,511,15,131071,127,15,4095,15,63,8191,15,31,8191,255,8191,31,1023,15,2047,8191,15,511,15,255,65535,262143,255,131071,524287,511,32767,1023,262143,15,131071,524287,511,31,511,262143,65535,511,32767,16383,511,31,31,65535,1023,524287,16383,2047,262143,4095,255,131071,65535,4095,4095,16383,524287,15,131071,16383,8191,65535,8191,63,1023,15,511,65535,1023,32767,16383,31,8191,262143,524287,131071,131071,1023,8191,4095,15,131071,16383,262143,262143,8191,262143,4095,8191,16383,1023,2047,131071,524287,31,15,15,4095,131071,65535,262143,2047,8191,31,4095,16383,65535,262143,15,65535,1023,2047,127,2047,262143,16383,65535,511,4095,262143,127,262143,15,127,524287,262143,127,1023,4095,255,524287,1023,1023,8191,262143,127,4095,4095,65535,31,16383,16383,15,524287,524287,255,63,16383,31,4095,31,31,65535,15,32767,2047,32767,255,127,2047,2047,511,65535,16383,131071,1023,255,32767,15,31,4095,127,4095,8191,524287,16383,511,127,8191,63,8191,2047,131071,511,63,15,511,15,262143,63,32767,16383,511,524287,131071,511,32767,63,262143,255,1023,262143,15,131071,262143,511,131071,262143,32767,127,511,2047,63,15,131071,255,1023,131071,15,15,1023,63,131071,31,255,31,255,65535,511,65535,4095,16383,8191,1023,127,63,31,65535,63,8191,4095,4095,2047,262143,16383,524287,511,511,63,255,8191,32767,65535,32767,16383,262143,32767,63,1023,8191,131071,511,1023,15,127,127,31,255,15,8191,63,1023,8191,131071,65535,31,2047,8191,4095,63,16383,255,131071,511,16383,32767,127,131071,511,127,8191,131071,15,524287,262143,255,127,8191,255,131071,31,2047,255,16383,1023,63,65535,127,32767,8191,511,31,16383,31,32767,262143,4095,32767,32767,15,63,511,65535,32767,4095,63,127,4095,131071,15,255,262143,131071,8191,32767,16383,31,4095,131071,15,255,255,65535,262143,511,65535,15,16383,65535,511,131071,31,8191,1023,511,15,524287,15,31,15,4095,16383,524287,1023,63,8191,63,32767,4095,15,2047,8191,15,16383,127,16383,131071,511,16383,131071,1023,511,262143,131071,4095,4095,16383,4095,131071,524287,2047,511,8191,63,131071,2047,127,32767,4095,524287,524287,2047,262143,255,524287,32767,255,2047,262143,511,8191,16383,524287,262143,32767,31,524287,511,2047,524287,2047,255,1023,8191,65535,131071,8191,15,511,262143,511,255,32767,1023,127,2047,31,15,2047,255,4095,131071,8191,15,127,63,2047,511,524287,4095,31,16383,31,31,31,16383,2047,524287,16383,524287,127,15,16383,8191,63,32767,4095,32767,15,4095,8191,31,15,8191,262143,16383,15,131071,255,63,2047,131071,16383,32767,31,4095,1023,4095,15,16383,262143,32767,65535,31,63,32767,127,31,255,4095,4095,16383,2047,524287,31,262143,65535,4095,127,63,511,65535,15,2047,8191,511,65535,15,262143,63,31,16383,131071,31,63,131071,511,524287,15,524287,4095,524287,255,8191,1023,4095,2047};
    }
}
